Snarls, pangenome deconstruction, and read mapping with vg giraffe
GET-A-PAN
Xian Chang & Jean Monlong
06/11/2025
Pangenome graph from assemblies
Built by aligning high-quality genomes, saved as paths through the pangenome.
Human Pangenome Reference Consortium (HPRC)
Liao, Asri, Ebler, et al. Nature 2023
Pangenome
With haplotype paths
Snarls, intuitively
Snarls, formal definition
A snarl is a subgraph bounded by two node sides that are:
- Separable: splitting each node into its two node sides separates a subgraph from the graph
Snarls, formal definition
A snarl is a subgraph bounded by two node sides that are:
- Separable: splitting the node into its two node sides separates a subgraph from the graph
Snarls, formal definition
A snarl is a subgraph bounded by two node sides that are:
Separable: splitting the node into its two node sides separates a subgraph from the graph
Minimal: there are no nodes within the snarl that are separable with either boundary node side
Snarls, formal definition
A snarl is a subgraph bounded by two node sides that are:
Separable: splitting the node into its two node sides separates a subgraph from the graph
Minimal: there are no nodes within the snarl that are separable with either boundary node side
Chains
A run of consecutive snarls and nodes is called a chain
Snarl decomposition
Snarls and chains can be nested inside of each other.
The nested relationship of snarls and chains is described by the snarl tree.
Snarl decomposition
Snarls and chains can be nested inside of each other.
The nested relationship of snarls and chains is described by the snarl tree.
Snarl decomposition
Snarls and chains can be nested inside of each other.
The nested relationship of snarls and chains is described by the snarl tree.
Snarl decomposition
Snarls and chains can be nested inside of each other.
The nested relationship of snarls and chains is described by the snarl tree.
Netgraphs
Netgraphs are a representation of snarls with their child chains collapsed into a single node
Snarl examples (vg deconstruct)
vcf + graph + decomposition for this graph
Snarl examples (vg deconstruct)
vcf + graph + decomposition for this graph
Snarl examples (vg deconstruct)
vcf + graph + decomposition for this graph
Snarl examples (vg deconstruct)
Trick for getting this snarl decomposition to look better (currently only for the distance index):
vg index -j [graph.dist] -w 6
vcf + graph + decomposition for this graph
Mapping reads with vg giraffe
Short reads
Long reads
Read mapping
Read mapping
Read mapping
Read mapping
Long read giraffe algorithm: Seeding
- Seeding with Minimizer Index
Long read giraffe algorithm: Chaining
- Seeding with Minimizer Index
- Chaining
Long read giraffe algorithm: Chaining
- Seeding with Minimizer Index
- Chaining
Long read giraffe algorithm: Chaining
- Seeding with Minimizer Index
- Chaining
Long read giraffe algorithm: Chaining
- Seeding with Minimizer Index
- Chaining
Long read giraffe algorithm: Chaining
- Seeding with Minimizer Index
- Chaining
Long read giraffe algorithm: Chaining
- Seeding with Minimizer Index
- Chaining
Long read giraffe algorithm: Chaining
- Seeding with Minimizer Index
- Chaining
Long read giraffe algorithm: Chaining
- Seeding with Minimizer Index
- Chaining
Long read giraffe algorithm: Chaining
- Seeding with Minimizer Index
- Chaining
Long read giraffe algorithm: Chaining
- Seeding with Minimizer Index
- Chaining
Long read giraffe algorithm: Zip code trees
- Seeding with Minimizer Index
- Zip code tree making with Distance Index
- Chaining with Zip Code Trees
Long read giraffe algorithm: Zip code trees
- Seeding with Minimizer Index
- Zip code tree making with Distance Index
- Chaining with Zip Code Trees
Long read giraffe algorithm: Zip code trees
- Seeding with Minimizer Index
- Zip code tree making with Distance Index
- Chaining with Zip Code Trees
Long read giraffe algorithm: Zip code trees
- Seeding with Minimizer Index
- Zip code tree making with Distance Index
- Chaining with Zip Code Trees
Long read giraffe algorithm: Zip code trees
- Seeding with Minimizer Index
- Zip code tree making with Distance Index
- Chaining with Zip Code Trees
Long read giraffe algorithm: Zip code trees
- Seeding with Minimizer Index
- Zip code tree making with Distance Index
- Chaining with Zip Code Trees
Long read giraffe algorithm: Zip code trees
- Seeding with Minimizer Index
- Zip code tree making with Distance Index
- Chaining with Zip Code Trees
Long read giraffe algorithm: Zip code trees
- Seeding with Minimizer Index
- Zip code tree making with Distance Index
- Chaining with Zip Code Trees
Long read giraffe algorithm: Zip code trees
- Seeding with Minimizer Index
- Zip code tree making with Distance Index
- Chaining with Zip Code Trees
Long read giraffe algorithm: Zip code trees
- Seeding with Minimizer Index
- Zip code tree making with Distance Index
- Chaining with Zip Code Trees
Long read giraffe algorithm: Alignment
- Seeding with Minimizer Index
- Zip code tree making with Distance Index
- Chaining with Zip Code Trees
- Alignment with GBWT/graph
Long read giraffe algorithm: Alignment
- Seeding with Minimizer Index
- Zip code tree making with Distance Index
- Chaining with Zip Code Trees
- Alignment with GBWT/graph
Long read giraffe algorithm: Alignment
- Seeding with Minimizer Index
- Zip code tree making with Distance Index
- Chaining with Zip Code Trees
- Alignment with GBWT/graph
Long read giraffe algorithm: Alignment
- Seeding with Minimizer Index
- Zip code tree making with Distance Index
- Chaining with Zip Code Trees
- Alignment with GBWT/graph
Long read giraffe algorithm: Alignment
- Seeding with Minimizer Index
- Zip code tree making with Distance Index
- Chaining with Zip Code Trees
- Alignment with GBWT/graph
Giraffe results
On the HPRC v2 graph which is x size?
